from collections import defaultdict


def FastAlign(seq1, seq2):
    #dlugosc ziarna identycznego
    identicalSeedLen = 3
    #dlugosc ziarna podobnego
    similarSeedLen = 2*identicalSeedLen
    
    print seq1
    print seq2
    
    #konstrukcja slownika identycznych podslow
    identicalSubwordsDict = defaultdict(list)
    
    #analiza pierwszej sekwencji
    for seed in xrange(len(seq1)-identicalSeedLen+1):
        seedKey = seq1[seed:seed+identicalSeedLen]
        
        #jesli to podslowo jeszcze nie istnieje w slowniku, tworze nowy klucz:
        if not identicalSubwordsDict.has_key(seedKey):
            identicalSubwordsDict[seedKey] = [[],[]]
        
        identicalSubwordsDict[seedKey][0].append(seed)

    #analiza drugiej sekwencji
    for seed in xrange(len(seq2)-identicalSeedLen+1):
        seedKey = seq2[seed:seed+identicalSeedLen]
        
        if not identicalSubwordsDict.has_key(seedKey):
            identicalSubwordsDict[seedKey] = [[],[]]
        
        identicalSubwordsDict[seedKey][1].append(seed)

    print "slownik slow identycznych:", identicalSubwordsDict
    
    #konstrukcja slownika podobnych podslow
    similarSubwordsDict = defaultdict(list)
    
    #wybieram krotsza sekwencje
    if len(seq1) <= len(seq2):
        shorterSeq = seq1
        longerSeq = seq2
    else:
        shorterSeq = seq2
        longerSeq = seq1

    #dla kazdego nowego podslowa tworze klucz w slowniku similarSubwordsDict
    for seed in xrange(len(shorterSeq)-similarSeedLen+1):
        seedKey = shorterSeq[seed:seed+similarSeedLen]
        
        #jesli to podslowo jeszcze nie istnieje, tworze nowy klucz:
        if not similarSubwordsDict.has_key(seedKey):
            similarSubwordsDict[seedKey] = [[],[]]
            
        #index dodaje to lokalizacje tego podslowa
        similarSubwordsDict[seedKey][0].append(seed)
        
    #tutaj szukam slow podobnych
    for pattern in similarSubwordsDict.keys():
        for text in similarSubwordsDict.keys():
            #parametr okreslajacy na ilu miejscach moze wystepowac roznica pomiedzy dwoma podobnymi ziarnami
            tolerance = 1
            index = 0
            
            #while nie skonczylem index nie wyczerpalem mozliwosci
            while pattern != text and index < len(text):
#                print pattern,text
                if pattern[index] != text[index]:
                    tolerance -= 1
                
                if tolerance < 0:
                    break
                
                #znalazlem podobienstwo, wiec dodaje do slownika
                if len(text) == index+1:
#                    print "PODOBNE PODSLOWA: ", pattern, text
                    similarSubwordsDict[pattern][1].append(text)
                    
                index += 1
                
    print "slownik slow podobnych:", similarSubwordsDict
            
    #tworze slownik gdzie kluczami sa podslowa podobne, a wartosciami listy slow do ktorych sa one podobne 
    #natomiast druga tablica w wartosciach zawiera lokalizacje podobnych podslow w drugiej sekwencji
    reverseSimilarSubwordsDict = defaultdict(list)
    for subword in similarSubwordsDict.keys():
        for similarWord in similarSubwordsDict[subword][1]:
            
            if not reverseSimilarSubwordsDict.has_key(similarWord):
                reverseSimilarSubwordsDict[similarWord] = [[],[]]
            
            reverseSimilarSubwordsDict[similarWord][0].append(subword)
        
    #tutaj szukam lokalizacji podslow podobnych w drugiej sekwencji            
    for seed in xrange(len(longerSeq)-similarSeedLen+1):
        seedKey = longerSeq[seed:seed+similarSeedLen]
        
        if reverseSimilarSubwordsDict.has_key(seedKey):
            reverseSimilarSubwordsDict[seedKey][1].append(seed)
            
    print "slownik slow podobnych do podobnych slow", reverseSimilarSubwordsDict      
               
    #segreguje podslowa w zaleznosci od tego na ktorej przekatnej leza;
    #klucz to numer przekatnych a wartosci to listy z lokalizacjami podslow identycznych
    identicalSeedLocations = defaultdict(list)
    
    #lece przez wszystkie identyczne podslowa
    for seedPosition in identicalSubwordsDict.values():
        #tutaj przez lokalizacje tych slow w pierwszej tablicy
        for firstSeqPosition in seedPosition[0]:
            #a tutaj w drugiej
            for secondSeqPosition in seedPosition[1]:
                #ustalam sobie klucz
                seedKey = (firstSeqPosition-secondSeqPosition)
#                print seedKey, firstSeqPosition, secondSeqPosition
                #jesli jeszcze go nie ma, to zaraz bedzie
                if not identicalSeedLocations.has_key(seedKey):
                    identicalSeedLocations[seedKey] = [[],[], []]
                    
                #przypisuje wartosc
                identicalSeedLocations[seedKey][0].append(firstSeqPosition)
                identicalSeedLocations[seedKey][1].append(secondSeqPosition)
                
   
    print "pozycje identycznych podslow:",identicalSeedLocations   
    
    #posortowanie wspolrzednych jednoczesnie w obu listach niczego nie zakluca, wiec 
    #sortuje poszczegolne wspolrzedne podslow tak, abym mogl je pozniej latwiej ocenic index polaczyc
    for diagonal in identicalSeedLocations:
        #sortowanie
        identicalSeedLocations[diagonal][0].sort()
        identicalSeedLocations[diagonal][1].sort()
        
        #glue0 to tablica do zalepienia malego gapa
        glue0 = []
        glue1 = []
        for index in xrange(len(identicalSeedLocations[diagonal][0])-1):
            
            current0 = identicalSeedLocations[diagonal][0][index]
            nextone0 = identicalSeedLocations[diagonal][0][index+1]
            
            current1 = identicalSeedLocations[diagonal][1][index]
            
            gap = nextone0-current0
            if gap > 1 and gap <= (identicalSeedLen)*2-1:
                #wypelniam zalepiacze dziur
                for i in xrange(1,gap):
                    glue0.append(current0+i)
                    glue1.append(current1+i)
        
        #zalepiam dziury        
        identicalSeedLocations[diagonal][0].extend(glue0)
        identicalSeedLocations[diagonal][1].extend(glue1)
        
        #ostatnie sortowanie
        identicalSeedLocations[diagonal][0].sort()
        identicalSeedLocations[diagonal][1].sort()
        
    print "Posortowane pozycje identycznych podslow index ocenione przekatne:",identicalSeedLocations   

    #licze scory i gapy
    for diagonal in identicalSeedLocations:
        diagonalScore = 0
        
        for index in xrange(len(identicalSeedLocations[diagonal][0])-1):
            current = identicalSeedLocations[diagonal][0][index]
            nextone = identicalSeedLocations[diagonal][0][index+1]
            
            if (nextone-current) == 1:
                diagonalScore += 1
            
            elif (nextone-current) < identicalSeedLen:
                for i in xrange(1, (nextone-current)):
                    diagonalScore += 1
            
            else:
                for i in xrange(identicalSeedLen-1, (nextone-current)):
                    diagonalScore -= 2
                
        identicalSeedLocations[diagonal][2].append(diagonalScore)
    
    bestDiagonals = {}
    for diagonal in identicalSeedLocations:
        bestDiagonals[identicalSeedLocations[diagonal][2][0]] = diagonal
         
    bestSortedIndexes = sorted(bestDiagonals, reverse=True)
    
    for i in bestSortedIndexes:
        print i,bestDiagonals[i]
    
    
    
    

def score(x, y):
    if x == y:
        return 2
    else:
        return -1
    
seq1 = "TTTGTTTTGCTGTGTCTGATTGATTGATTCATTTTTAAGACACTGACTATCCCATACATAATATTAAATACACATTAAGGATTGGAACAATTTTATCACATTAAGAATGAACTGCACCAGTTACATTCATGCCCTGGGTTTCCTTTATGCCTTACAAGCAGGAGGACAAACTAAAATTAAAGTTGCCTCATCCATTTGAAAGTTTTCAAATCTAGACGCACACCTGAACAGTAGTTATTTGTTAATGCCCTTCTTCTCCAACAAATACCCACCTCTCATACTTATGTTCACTTGCCATTTAGAATGTACTGGACTTCTGAGATTCACAAACTTTTGTGA"
seq2 = "CTTGTTTTGTTGTGCTTGATTGGTTGGTTTTTAAGACACTGCTGAAGGAAATAGTTATTCCATCTATGTTATTAAATATATATTAGGGGCTGGGGCAATTTTACATTGTCAAGAATGAACTTCACTGCTCACATGCATGCCCCAGGTTTCCATTATCTTTCAGAAGCAGTAAGACTAACTAAATTTAAAGTTGCCTCATACATTTGAAAGTTTTCAAACCTGAACCAATAACCTGAATGGTAGTTATTGGCAAAAGCACCA"

FastAlign(seq1, seq2)
